package leetcode_61_80;

import com.sun.org.apache.xerces.internal.impl.dv.util.ByteListImpl;
import utils.ListNode;

import java.util.ArrayList;
import java.util.List;

public class rotateRight_61 {
    /**
     * 给一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        /**
        通过一个集合维护链表所有数值
        然后顺序处理链表
         */
        if(k==0 || head==null)
            return head;

        List<Integer> nodeVal=new ArrayList<>();

        ListNode root0=new ListNode(0);
        root0.next=head;  //便于处理
        int len=0;
        while (root0.next!=null){
            nodeVal.add(root0.next.val);          //把链表中的值放入集合中
            len++;
            root0=root0.next;
        }
        //处理k
        k=k>len?k%len:k;
        if(k==0)
            return head;
        ListNode root1=new ListNode(0);
        root1.next=head;  //便于处理
        int count=0,index=0;
        while (root1.next!=null){
            if(count<k){       //前k个节点
                int idx=len+count-k;   //算出此时链表的节点值来自链表哪个元素
                root1.next.val=nodeVal.get(idx);
            }
            else//从链表第k+1个节点开始处理
                root1.next.val=nodeVal.get(index++);   //从集合的值赋值给节点
            count++;
            root1=root1.next;
        }
        return head;
    }

    /**
     * 思路是，不必进行节点的数值变化
     * 可以闭合成环，找到位移后新的开始节点，再断开返回即可
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight2(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        //计算出链表的长度 n，
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        //新链表的最后一个节点为原链表的第 (n−1)−(k mod n) 个节点（从 0 开始计数）。
        int end = n - k % n;
        if (end == n)
            return head;
        iter.next = head;   //此时 iter 是该链表的末尾节点，将其与头节点相连
        while (end-- > 0) {   //找到end位置
            iter = iter.next;
        }
        //将当前闭合为环的链表断开，即可得到我们所需要的结果。
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }

}
